class Solution:
    def countSubstrings(self, s: str) -> int:
        t = '#'.join("^" + s + "$")
        h_len = [0] * (len(t) - 2)
        h_len[1] = 1
        ans = box_m = box_r = 0
        for i in range(2, len(h_len)):
            cur_l = 1  # 初始化为 1
            if i < box_r:
                cur_l = min(h_len[box_m * 2 - i], box_r - i)

            while t[i - cur_l] == t[i + cur_l]:

                cur_l += 1
                box_m, box_r = i, i + cur_l

            h_len[i] = cur_l
            ans+=cur_l//2
        return ans